package com.shm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 20. 表示数值的字符串
 * 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
 * 例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，
 * 但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。
 * @author SHM
 */
public class IsNumber {
    public boolean isNumber(String s) {
        // s为空对象或 s长度为0(空字符串)时, 不能表示数值
        if(s == null || s.length() == 0){
            return false;
        }
        // 标记是否遇到数位、小数点、‘e’或'E'
        boolean isNum = false, isDot = false, ise_or_E = false;
        // 删除字符串头尾的空格，转为字符数组，方便遍历判断每个字符
        char[] str = s.trim().toCharArray();

        for(int i=0; i<str.length; i++) {
            // 判断当前字符是否为 0~9 的数位
            if(str[i] >= '0' && str[i] <= '9') {
                isNum = true;
            } else if(str[i] == '.') {
                // 遇到小数点
                // 小数点之前可以没有整数，但是不能重复出现小数点、或出现‘e’、'E'
                if(isDot || ise_or_E){
                    return false;
                }
                // 标记已经遇到小数点
                isDot = true;
            } else if(str[i] == 'e' || str[i] == 'E') {
                // 遇到‘e’或'E'

                // ‘e’或'E'前面必须有整数，且前面不能重复出现‘e’或'E'
                if(!isNum || ise_or_E) {
                    return false;
                }
                // 标记已经遇到‘e’或'E'
                ise_or_E = true;
                // 重置isNum，因为‘e’或'E'之后也必须接上整数，防止出现 123e或者123e+的非法情况
                isNum = false;
            } else if(str[i] == '-' ||str[i] == '+') {
                // 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置
                if(i!=0 && str[i-1] != 'e' && str[i-1] != 'E'){
                    return false;
                }
            } else {
                // 其它情况均为不合法字符
                return false;
            }
        }
        return isNum;
    }


    /**
     * 解题思路：
     * 本题使用有限状态自动机。根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。
     *
     * 字符类型：
     *
     * 空格 「 」、数字「 0—90—9 」 、正负号 「 +-+− 」 、小数点 「 .. 」 、幂符号 「 eEeE 」 。
     *
     * 状态定义：
     *
     * 按照字符串从左到右的顺序，定义以下 9 种状态。
     *
     * 开始的空格
     * 幂符号前的正负号
     * 小数点前的数字
     * 小数点、小数点后的数字
     * 当小数点前为空格时，小数点、小数点后的数字
     * 幂符号
     * 幂符号后的正负号
     * 幂符号后的数字
     * 结尾的空格
     * 结束状态：
     *
     * 合法的结束状态有 2, 3, 7, 8 。
     *
     *
     *
     * 算法流程：
     * 初始化：
     *
     * 状态转移表 statesstates ： 设 states[i]states[i] ，其中 ii 为所处状态， states[i]states[i] 使用哈希表存储可转移至的状态。键值对 (key, value)(key,value) 含义：若输入 keykey ，则可从状态 ii 转移至状态 valuevalue 。
     * 当前状态 pp ： 起始状态初始化为 p = 0p=0 。
     * 状态转移循环： 遍历字符串 ss 的每个字符 cc 。
     *
     * 记录字符类型 tt ： 分为四种情况。
     * 当 cc 为正负号时，执行 t = 's' ;
     * 当 cc 为数字时，执行 t = 'd' ;
     * 当 cc 为 e , E 时，执行 t = 'e' ;
     * 当 cc 为 . , 空格 时，执行 t = c （即用字符本身表示字符类型）;
     * 否则，执行 t = '?' ，代表为不属于判断范围的非法字符，后续直接返回 falsefalse 。
     * 终止条件： 若字符类型 tt 不在哈希表 states[p]states[p] 中，说明无法转移至下一状态，因此直接返回 FalseFalse 。
     * 状态转移： 状态 pp 转移至 states[p][t]states[p][t] 。
     * 返回值： 跳出循环后，若状态 p \in {2, 3, 7, 8}p∈2,3,7,8 ，说明结尾合法，返回 TrueTrue ，否则返回 FalseFalse 。
     *
     * 复杂度分析：
     * 时间复杂度 O(N)O(N) ： 其中 NN 为字符串 ss 的长度，判断需遍历字符串，每轮状态转移的使用 O(1)O(1) 时间。
     * 空间复杂度 O(1)O(1) ： statesstates 和 pp 使用常数大小的额外空间。
     *
     * 作者：jyd
     * 链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/mian-shi-ti-20-biao-shi-shu-zhi-de-zi-fu-chuan-y-2/
     * @param s
     * @return
     */
    public boolean isNumber_2(String s) {
        Map[] states = {
                // 0.
                new HashMap() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }},
                // 1.
                new HashMap() {{ put('d', 2); put('.', 4); }},
                // 2.
                new HashMap() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }},
                // 3.
                new HashMap() {{ put('d', 3); put('e', 5); put(' ', 8); }},
                // 4.
                new HashMap() {{ put('d', 3); }},
                // 5.
                new HashMap() {{ put('s', 6); put('d', 7); }},
                // 6.
                new HashMap() {{ put('d', 7); }},
                // 7.
                new HashMap() {{ put('d', 7); put(' ', 8); }},
                // 8.
                new HashMap() {{ put(' ', 8); }}
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') {
                t = 'd';
            }
            else if(c == '+' || c == '-'){
                t = 's';
            }
            else if(c == 'e' || c == 'E') {
                t = 'e';
            }
            else if(c == '.' || c == ' '){
                t = c;
            } else{
                t = '?';
            }
            if(!states[p].containsKey(t)) {
                return false;
            }
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}
